`
https://leetcode.cn/problems/lexicographically-smallest-palindromic-permutation-greater-than-target/
`

/**
 * @param {string} s
 * @param {string} target
 * @return {string}
 */
var lexPalindromicPermutation = function (s, target) {
  const n = s.length
  const halfLen = Math.floor(n / 2)
  const counter = {}
  const hasNeg = () => {
    return Object.values(counter).some((n) => n < 0)
  }
  // 将 counter 里的字符按字典序构建成字符串
  const buildStr = () => {
    const res = []
    for (const c of 'abcdefghijklmnopqrstuvwxyz') {
      if (counter[c]) {
        res.push(c.repeat(counter[c] / 2))
      }
    }
    return res.join('')
  }

  // 统计 s
  for (const c of s) {
    counter[c] = (counter[c] || 0) + 1
  }

  // 记录回文串中间的字符
  let midCh = ''
  // 处理奇数
  for (const ch in counter) {
    if (counter[ch] % 2 === 0) continue

    // 回文串不可能有两个奇数数量的字符
    if (midCh) return ""

    midCh = ch
    counter[ch]--
  }

  // 消耗掉 target，假设左右两半相同
  for (let i = 0; i < halfLen; i++) {
    const c = target[i]
    counter[c] = (counter[c] || 0) - 2
  }

  // 特殊情况：target 左半直接翻转就比 target 大，直接返回
  if (!hasNeg()) {
    const leftS = target.substring(0, halfLen)
    const rightS = midCh + leftS.split('').reverse().join('')
    const res = leftS + rightS
    if (res > target) return res
  }

  // 从后面开始尝试
  for (let i = halfLen - 1; i >= 0; i--) {
    const c = target[i]
    // 撤销消耗
    counter[c] = (counter[c] || 0) + 2
    // 如果有负数说明无法做到全部都一样
    if (hasNeg()) continue

    // 找到，不断增大 target[i]
    for (let j = c.charCodeAt(0) - 'a'.charCodeAt(0) + 1; j < 26; j++) {
      const ch = String.fromCharCode(j + 'a'.charCodeAt(0))
      // ch 字符用完了
      if (!counter[ch]) continue

      // 找到答案，答案由三部分组成
      // 前面还没找的部分 + 找到的不断增大的字符 + counter 里剩下的字符按字典序排回去
      counter[ch] -= 2
      const res = target.substring(0, i) + ch + buildStr()
      // 构建回文
      return res + midCh + res.split('').reverse().join('')
    }
  }
  return ""
};